import org.junit.jupiter.api.Assertions;
import org.junit.jupiter.api.Test;

/**
 * 1027.最长等差数列
 * 给你一个整数数组 nums，返回 nums 中最长等差子序列的长度。
 *
 * 回想一下，nums 的子序列是一个列表 nums[i1], nums[i2], ..., nums[ik] ，且 0 <= i1 < i2 < ... < ik <= nums.length - 1。
 * 并且如果 seq[i+1] - seq[i]( 0 <= i < seq.length - 1) 的值都相同，那么序列 seq 是等差的。
 */
public class LongestArithSeqLength {

    @Test
    public void test1() {
        Assertions.assertEquals(4, longestArithSeqLength(new int[]{3, 6, 9, 12}));
    }

    @Test
    public void test2() {
        Assertions.assertEquals(3, longestArithSeqLength(new int[]{9, 4, 7, 2, 10}));
    }


    @Test
    public void test3() {
        Assertions.assertEquals(4, longestArithSeqLength(new int[]{20, 1, 15, 3, 10, 5, 8}));
    }


    @Test
    public void test4() {
        Assertions.assertEquals(4, longestArithSeqLength(new int[]{12, 28, 13, 6, 34, 36, 53, 24, 29, 2, 23, 0, 22, 25, 53, 34, 23, 50, 35, 43, 53, 11, 48, 56, 44, 53, 31, 6, 31, 57, 46, 6, 17, 42, 48, 28, 5, 24, 0, 14, 43, 12, 21, 6, 30, 37, 16, 56, 19, 45, 51, 10, 22, 38, 39, 23, 8, 29, 60, 18
        }));
    }

    @Test
    public void test5() {
        Assertions.assertEquals(2, longestArithSeqLength(new int[]{83, 20, 17, 43, 52, 78, 68, 45}));
    }

    public int longestArithSeqLength(int[] nums) {

//      dp[i] 为 以nums[i]结尾，公差为500+d时的最大等差数列的长度
        int[][] dp = new int[nums.length][1001];

        int maxSequenceLength = 1;
        for (int i = 1; i < nums.length; i++) {


            for (int j = 0; j < i; j++) {
                int diff = nums[i] - nums[j] + 500;

                dp[i][diff] = dp[j][diff] + 1;
                maxSequenceLength = Math.max(maxSequenceLength, dp[i][diff]);

            }
        }

        return maxSequenceLength + 1;
    }
}
